The Point In Polygon (PIP) problem has important implications in a variety of disciplines, including geographic positioning systems (GPS), computer games, computer vision applications, mapping applications, computer-aided designs (CAD) and others. Some solutions of the PIP problem have been motivated by the requirements of determining a relative location of a given user device with respect to a geographical region or area.
For example, it might be useful to determine whether a given user of a device is located inside or outside a given area of interest (AOI) such as, for example, a city, a park, a festival venue and the like. In this example, the digitized boundaries of the given AOI may contain hundreds of thousands of points. Hence, application of a “brute force” validation technique for determining whether the location of the device is within the boundaries of the AOI in order to solve the PIP problem involves a large number of comparisons of the location of the device against all of the many segments of a polygon representing the boundary of the given AOI. While some performance optimizations exist for solving the PIP problem, in general such optimizations are still resource intensive or impractical. Consequently, validating the relative location of data points against a large boundary is computationally expensive.
Therefore, improvements to solutions of the PIP problem may be desirable.